package org.wuxinshui.boosters.nowcoder.classicQuestion;

import java.util.HashMap;
import java.util.Stack;

/**
 * 描述
 * <p>
 * 计算逆波兰式（后缀表达式）的值
 * 运算符仅包含"+","-","*"和"/"，被操作数是整数
 * <p>
 * 保证表达式合法，除法时向下取整。
 * <p>
 * 数据范围：表达式的长度满足：n≤10000
 * 进阶：空间复杂度O(n) ， 时间复杂度O(n)
 * 例如：
 * ["20", "10", "+", "30", "*"] -> ((20 + 10) * 30) -> 900
 * ["40", "130", "50", "/", "+"] -> (40 + (130 / 50)) -> 42
 * 示例1
 * <p>
 * 输入：["20","10","+","30","*"]
 * 返回值：900
 * 示例2 输入：["20"]
 * <p>
 * 返回值：20
 */
public class CC2EvalRPN {
    /**
     *
     * @param tokens string字符串一维数组
     * @return int整型
     */
    public  int evalRPN(String[] tokens) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                Integer a = stack.pop();
                Integer b = stack.pop();

                switch (token) {
                    case "+":
                        stack.push((a + b));
                        break;
                    case "-":
                        stack.push(a - b);
                        break;

                    case "*":
                        stack.push(a * b);
                        break;
                    case "/":
                        stack.push(a / b);
                        break;
                    default:
                        throw new IllegalArgumentException("参数错误");
                }
            }
        }


        return stack.pop();
    }

    public boolean isNumber(String token) {
        try {
            Integer.parseInt(token);
        } catch (NumberFormatException e) {
            return false;
        }

        return true;
    }

    public static void main(String[] args) {
        // 中缀表达式: (3 + 4) × 5
        String infix = "(3 + 4) * 5";

        // 转换为逆波兰式
        String rpn = infixToRPN(infix);
        System.out.println("中缀表达式: " + infix);
        System.out.println("逆波兰式: " + rpn); // 输出: 3 4 + 5 *

        // 计算逆波兰式
        CC2EvalRPN evalRPN=new CC2EvalRPN();
        String[] array=rpn.split("\\s+");
        int result = evalRPN.evalRPN(array);
        System.out.println("计算结果: " + result); // 输出: 35
    }

    // 定义运算符优先级
    private static HashMap<Character, Integer> precedence = new HashMap<>();
    static {
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);
        precedence.put('^', 3);
    }

    public static String infixToRPN(String infix) {
        StringBuilder output = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (char c : infix.toCharArray()) {
            if (Character.isDigit(c)) {
                // 数字直接输出
                output.append(c).append(' ');
            } else if (c == '(') {
                // 左括号入栈
                stack.push(c);
            } else if (c == ')') {
                // 右括号：弹出直到遇到左括号
                while (!stack.isEmpty() && stack.peek() != '(') {
                    output.append(stack.pop()).append(' ');
                }
                stack.pop(); // 弹出左括号
            } else if (precedence.containsKey(c)) {
                // 运算符：弹出优先级更高或相等的运算符
                while (!stack.isEmpty() && stack.peek() != '(' &&
                        precedence.getOrDefault(stack.peek(), 0) >= precedence.get(c)) {
                    output.append(stack.pop()).append(' ');
                }
                stack.push(c);
            }
        }

        // 弹出栈中剩余运算符
        while (!stack.isEmpty()) {
            output.append(stack.pop()).append(' ');
        }

        return output.toString().trim();
    }
}
